'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-19 21:25:24
'''
'''
312. 戳气球
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:

输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

tips: 这个过程需要反过来想。dp[i][j]表示i,j气球相邻了。这个时候向其中插入一个气球k。即在i，j相邻前弄爆的
气球k，这个时候分值最大，则要求
dp[i][j] = max(dp[i][j], val[k]*val[i]*val[j]+dp[i][k]+dp[k][j])
最优子结构，无后效性。
看转移方程可以看出，i，j值的得出，需要i，j之间的dp值都存在。这个时候可以采用i从n-1递减，j从i+2递增到n+1。或者
j从2递增，i从j-2递减。都能达到这个目的。注意边界处理。
'''
from typing import List
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        from sys import maxsize
        dp = [[0]*(len(nums)+2) for _ in nums+[0, 1]]
        val = [1] + nums + [1]
        n = len(nums)
        for i in range(n-1, -1, -1):
            for j in range(i+2, n+2):
                for k in range(i+1, j):
                    total = val[k]*val[i]*val[j]
                    total += dp[i][k]+dp[k][j]
                    dp[i][j] = max(dp[i][j], total)
        # for j in range(2, n+2):
        #     for i in range(j-1, -1, -1):
        #         for k in range(i+1, j):
        #             total = val[k]*val[i]*val[j]
        #             total += dp[i][k]+dp[k][j]
        #             dp[i][j] = max(dp[i][j], total)
        
        return dp[0][n+1]
if __name__ == "__main__":
    solution = Solution()
    nums = [3,1,5,8]
    print(solution.maxCoins(nums))